//Author:	ZouTongCheng
//Time:		2021.9.26

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cassert>
using namespace std;

class State {
public:
	State(vector<int>, int, int);		//初始化数据
	vector<State> GetNextStates(State);	//获取当前状态的后继状态
	vector<int> GetArr();
	int GetHash();						//通过hash判重
	bool Compare(State);				//比较两State是否相等
	void PrintResult();					//输出结果
	static int GetDistance(vector<int>, vector<int>);			//获取h(n)
	State GetNextState(vector<int>, vector<int>, int, int, int);
	int GetWeight();

	bool operator < (State a) const {
		return weight > a.GetWeight();
	}

	static double g_w, h_w;

private:
	vector<int> arr;
	int weight;		//相当于f(n)
	int step;		//相当于g(n)
};

double State::g_w = 1;
double State::h_w = 1;

State::State(vector<int> arr, int formerStep, int distance) {
	this->arr = arr;
	this->step = formerStep + 1;
	this->weight = this->step * g_w + distance * h_w;
}

vector<int> State::GetArr() {
	return arr;
}

bool State::Compare(State u) {
	vector<int> uArr = u.GetArr();	
	for (int i = 0; i < 8; i ++) {
		if (uArr[i] != this->arr[i]) return false;
	}
	return true;
}

int State::GetWeight() {
	return weight;
}

int State::GetHash() {
	const int MOD = 1000007;
	long long hash = 0;
	for (int x : this->arr) {
		hash = ((hash + x * 71) * 100000007 + 99999997) % MOD;
	}
	return hash;
}

void State::PrintResult() {
	cout << "Target get." << endl;
	cout << "The totol step = " << this->step << endl;
	for (int i = 0; i < 9; i ++) {
		cout << this->arr[i];
		if (i % 3 == 2) cout << endl;
		else cout << " ";
	}
}

int State::GetDistance(vector<int> a, vector<int> b) {
	int cnt = 0;
	for (int i = 0; i < 9; i ++) {
		if (a[i] != b[i]) cnt ++;
	}
	return cnt;
}

State State::GetNextState(vector<int> nextArr, vector<int> targetArr, int s, int t, int step) {
	swap(nextArr[s], nextArr[t]);
	int distance = GetDistance(nextArr, targetArr);	
	return *(new State(nextArr, step, distance));
}

vector<State> State::GetNextStates(State target) {
	vector<State> lst;
	vector<int> targetArr = target.GetArr();

	int zero;
	for (int i = 0; i < 9; i ++) {
		if (this->arr[i] == 0) {
			zero = i;
			break;
		}
	}

	if (zero - 3 >= 0) {
		lst.push_back(GetNextState(this->arr, targetArr, zero, zero - 3, this->step));
	}
	if (zero + 3 < 9) {
		lst.push_back(GetNextState(this->arr, targetArr, zero, zero + 3, this->step));
	}
	if (zero - 1 >= 0) {
		lst.push_back(GetNextState(this->arr, targetArr, zero, zero - 1, this->step));
	}
	if (zero + 1 < 9) {
		lst.push_back(GetNextState(this->arr, targetArr, zero, zero + 1, this->step));
	}

	return lst;
}

void A_Search(State start, State target) {
	priority_queue<State> que;		//通过优先队列实现按f(n)排序选取后继状态
	que.push(start);
	bool hash_map[1000007] = {false};

	while(!que.empty()) {
		State u = que.top();
		que.pop();

		if (target.Compare(u)) {
			u.PrintResult();
			return;
		}

		vector<State> nextStates = u.GetNextStates(target);
		for (State v : nextStates) {
			int hash = v.GetHash();
			if (hash_map[hash]) continue;
			hash_map[hash] = true;
			que.push(v);
		}
	}

	cout << "No Answer";
}

bool CheckInput(vector<int> arr) {		//验证输入格式,其中棋盘空格以0代替
	if (arr.size() != 9) return false;
	bool vis[9] = {false};
	for (int x : arr) {
		if (x > 8 || x < 0) return false;
		if (vis[x]) return false;
		vis[x] = true;
	}
	return true;
}

void Run() {
	cout << "input the weight of g(x) and h(x)\n";
	cin >> State::g_w >> State::h_w;

	
	cout << "input the initial graph\n";
	vector<int> start, target;
	for (int i = 1; i <= 9; i ++) {
		int x;
		cin >> x;
		start.push_back(x);
	}
	for (int i = 1; i <= 9; i ++) {
		int x;
		cin >> x;
		target.push_back(x);
	}
	
	assert(CheckInput(start));
	assert(CheckInput(target));

	State startState = *(new State(start, -1, 0));
	State targetState = *(new State(target, -1, 0));
	A_Search(startState, targetState);
}

int main() {
	freopen("i.in", "r", stdin);
	freopen("o.out", "w", stdout);
	Run();
}
